﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class FiniteStateMachine : IEnumerable<State>
{
    #region Fields

    public static readonly string Epsilon = String.Empty;

    private HashSet<string> language;
    private Dictionary<string, State> states;
    private Dictionary<string, State> finalStates;
    private State startState;
    private string epsilonName;
    private string emptySetName;

    #endregion

    #region Constructors

    public FiniteStateMachine()
    {
        this.language = new HashSet<string>();
        this.states = new Dictionary<string, State>();
        this.finalStates = new Dictionary<string, State>();
        this.epsilonName = "Epsilon";
        this.emptySetName = "EmptySet";
    }

    public FiniteStateMachine(string epsilonName, string emptySetName)
        : this()
    {
        this.EpsilonName = epsilonName;
        this.EmptySetName = emptySetName;
    }

    #endregion

    #region Properties

    public ICollection<string> Language
    {
        get
        {
            return this.language;
        }
    }

    public HashSet<string> LanguageSet
    {
        get
        {
            return this.language;
        }
    }

    public State StartState
    {
        get
        {
            return this.startState;
        }
    }

    public string StartStateValue
    {
        get
        {
            return this.startState.Name;
        }
    }

    public int Count
    {
        get
        {
            return states.Count;
        }
    }

    public int FinalStatesCount
    {
        get
        {
            return finalStates.Count;
        }
    }

    public string EpsilonName
    {
        get
        {
            return this.epsilonName;
        }
        set
        {
            this.epsilonName = value;
        }
    }

    public string EmptySetName
    {
        get
        {
            return this.emptySetName;
        }
        set
        {
            this.emptySetName = value;
        }
    }

    #endregion

    #region Methods

    public bool AddState(string name)
    {
        if (states.ContainsKey(name))
        {
            return false;
        }
        State state = new State(name);
        this.states.Add(name, state);
        return true;
    }

    public bool AddStateToFinalStates(string name)
    {
        State state;
        if (states.ContainsKey(name))
        {
            state = states[name];
            if (this.finalStates.ContainsKey(name))
            {
                return false;
            }
            this.finalStates.Add(name, state);
            return true;
        }
        return false;
    }

    public bool AddTransition(string from, string to, params string[] values)
    {
        if (!states.ContainsKey(from) || !states.ContainsKey(to))
        {
            return false;
        }
        FillLanguage(values);
        State fromState = states[from];
        State toState = states[to];
        Transition transition = new Transition(fromState, toState, values);
        fromState.AddTransition(transition);
        return true;
    }

    public bool SetStartState(string name)
    {
        State state;
        if (states.ContainsKey(name))
        {
            state = states[name];
            this.startState = state;
            return true;
        }
        return false;
    }

    private void FillLanguage(ICollection<string> values)
    {
        foreach (string value in values)
        {
            language.Add(value);
        }
    }

    public string ToFullString()
    {
        string line = new string('-', 50);
        StringBuilder output = new StringBuilder();
        output.AppendLine(line);
        output.AppendLine(String.Format("StartState = {0}", this.StartState));
        output.AppendLine();
        output.Append("FinalStates = {");
        foreach (var pair in this.finalStates)
        {
            output.AppendFormat("{0}, ", pair.Value);
        }
        output.Remove(output.Length - 2, 2);
        output.AppendLine("}");
        output.AppendLine();

        foreach (var pair in this.states)
        {
            output.Append(pair.Value.ToFullString(this.epsilonName));
        }
        output.AppendLine(line);
        return output.ToString();
    }

    public override string ToString()
    {
        StringBuilder output = new StringBuilder();
        foreach (var pair in states)
        {
            output.AppendFormat("{0}, ", pair.Value);
        }
        output.Remove(output.Length - 2, 2);

        return output.ToString();
    }

    public IEnumerator<State> GetEnumerator()
    {
        foreach (var pair in this.states)
        {
            yield return pair.Value;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion

    #region Algorithm methods

    public bool IsDeterministic()
    {
        State state;
        foreach (var pair in this.states)
        {
            state = pair.Value;
            if (state.IsDeterministic(this.language))
            {
                continue;
            }
            return false;
        }
        return true;
    }

    public FiniteStateMachine ToDeterministic()
    {
        FiniteStateMachine machine = new FiniteStateMachine();
        List<State> currentStates = new List<State>();
        currentStates.Add(startState);
        EpsilonClosed(currentStates);
        HashSet<string> usedStates = new HashSet<string>();
        Dictionary<string, HashSet<string>> statesUsed = new Dictionary<string, HashSet<string>>();
        foreach (string languageElement in language)
        {
            statesUsed.Add(languageElement, new HashSet<string>());
        }
        Queue<List<State>> queue = new Queue<List<State>>();
        queue.Enqueue(currentStates);
        string currentStateName = ConstructStateName(currentStates);
        machine.AddState(currentStateName);
        machine.SetStartState(currentStateName);
        List<State> nextStateAsList;
        bool isFinalState = false;
        while (queue.Count > 0)
        {
            currentStates = queue.Dequeue();
            currentStateName = ConstructStateName(currentStates);
            usedStates.Add(currentStateName);
            
            foreach (string languageElement in language)
            {
                nextStateAsList = new List<State>();
                if (languageElement == Epsilon)
                {
                    continue;
                }
                foreach (State state in currentStates)
                {
                    if (this.finalStates.ContainsKey(state.Name))
                    {
                        isFinalState = true;
                    }
                    foreach (Transition transition in state)
                    {
                        if (transition.Contains(languageElement))
                        {
                            nextStateAsList.Add(transition.To);
                        }
                    }
                }

                string nextStateName;
                EpsilonClosed(nextStateAsList);
                nextStateName = ConstructStateName(nextStateAsList);
                machine.AddState(nextStateName);

                HashSet<string> statesSet = statesUsed[languageElement];
                if (!statesSet.Contains(currentStateName))
                {
                    statesSet.Add(currentStateName);
                    machine.AddTransition(currentStateName, nextStateName, languageElement);
                    if (isFinalState)
                    {
                        machine.AddStateToFinalStates(currentStateName);
                    }
                    queue.Enqueue(nextStateAsList);
                }
                isFinalState = false;
            }
        }

        return machine;
    }

    private string ConstructStateName(ICollection<State> states)
    {
        StringBuilder stateName = new StringBuilder();
        if (states.Count > 0)
        {
            stateName.Append("{");
            foreach (State state in states)
            {
                stateName.AppendFormat("{0}, ", state.Name);
            }
            stateName.Remove(stateName.Length - 2, 2);
            stateName.Append("}");
        }
        else
        {
            stateName.Append(this.emptySetName);
        }

        return stateName.ToString();
    }

    public void EpsilonClosed(ICollection<State> states)
    {
        Queue<State> queue = new Queue<State>();
        foreach (State state in states)
        {
            queue.Enqueue(state);
        }

        State currentState;
        while (queue.Count > 0)
        {
            currentState = queue.Dequeue();

            foreach (Transition transition in currentState)
            {
                if (transition.ContainsEpsilon())
                {
                    queue.Enqueue(transition.To);
                    states.Add(transition.To);
                }
            }
        }
    }

    #endregion
}